#include "lsdSort.h"
#include "util.h"

void lsdSortInts(int a[], int n)
{

    UTIL_ASSERT(a != nullptr);
    UTIL_ASSERT(n >= 1);

    const int bits_per_byte = 8; 
    const int BITS = 32;
    const int R = 1 << bits_per_byte;
    const int MASK = R - 1 ;
    const int w = BITS / bits_per_byte;

    int *aux = (int *)util_malloc(n * w);
    
    for(int d = 0; d < w; d++)
    {
        int count[R+1];
        util_memset(count, 0, (R+1)*w);

        for(int i = 0; i < n; i++)
        {
            int c = (a[i] >> bits_per_byte * d) & MASK;
            count[c+1]++;
        }

        for(int i = 0; i < R; i++)
        {
            count[i+1] += count[i];
        }
        if(d == w-1)
        {
            int shift1 = count[R] - count[R/2];
            int shift2 = count[R/2];

            for(int r = 0; r < R/2; r++)
            {
                count[r] += shift1;
            }
            for(int r = R/2; r < R; r++)
            {
                count [r] -= shift2;
            }
        }

        for(int i = 0; i < n; i++)
        {
            int c = (a[i] >> bits_per_byte * d) & MASK;
            aux[count[c]++] = a[i];
        }

        for(int i = 0; i < n; i++)
        {
            a[i] = aux[i];
        }
    }
    util_free(aux);
    
}
